-------------------------------
--$Id
-------------------------------
--[[
	数据结构工具类
]]

local math_floor = math.floor
local os_time = os.time
local printx = debug.printx

--双向链表基类 只有头尾节点指针 多余的东东去扩展
clsBaseDLink = clsObject:Inherit("clsBaseDLink")
function clsBaseDLink:OnCreate(name)
	Super(clsBaseDLink).OnCreate(self)
	self.m_Name = name
	self:Reset()
end

function clsBaseDLink:ToString()
	return self.m_Name
end

function clsBaseDLink:Reset()
	self.m_Header = nil --头节点
	self.m_Tail = nil --尾节点
end

function clsBaseDLink:OnDestroy()
	Super(clsBaseDLink).OnDestroy(self)
	self:Reset()
end

--获取头节点
function clsBaseDLink:GetHeaderNode()
	return self.m_Header
end

--获取尾节点
function clsBaseDLink:GetTailNode()
	return self.m_Tail
end

--删除所有节点
function clsBaseDLink:Clear()
	while self.m_Header do
		if self.m_Header == self.m_Tail then
			self.m_Header = nil
			self.m_Tail = nil
		else
			local preNode = self.m_Header.Pre
			preNode.Next = nil
			self.m_Header.Pre = nil
			self.m_Header = preNode
		end
	end
end

--删除节点
function clsBaseDLink:RemoveNode(node)
	if node == self.m_Header then
		self:RemoveHeaderNode()
	elseif node == self.m_Tail then
		self:RemoveTailNode()
	else
		local preNode = node.Pre
		local nextNode = node.Next
		assert(preNode and nextNode)

		nextNode.pre = preNode
		preNode.Next = nextNode
		node.Next = nil
		node.Pre = nil
	end
end

--删除头节点
function clsBaseDLink:RemoveHeaderNode()
	if self.m_Header == self.m_Tail then
		self.m_Header = nil
		self.m_Tail = nil
	else
		local preNode = self.m_Header.Pre
		preNode.Next = nil
		self.m_Header.Pre = nil
		self.m_Header = preNode
	end
end

--删除尾节点
function clsBaseDLink:RemoveTailNode()
	if self.m_Header == self.m_Tail then
		self.m_Header = nil
		self.m_Tail = nil
	else
		local nextNode = self.m_Header.Next
		nextNode.Pre = nil
		self.m_Tail.Next = nil
		self.m_Tail = nextNode
	end
end

--增加节点到头部
function clsBaseDLink:AddNodeToHeader(node)
	if not self.m_Header then
		self.m_Header = node
		self.m_Tail = node
	else
		self.m_Header.Next = node
		node.Pre = self.m_Header
		self.m_Header = node
	end
end

--增加节点到尾部
function clsBaseDLink:AddNodeToTail(node)
	if not self.m_Header then
		self.m_Header = node
		self.m_Tail = node
	else
		self.m_Tail.Pre = node
		node.Next = self.m_Tail
		self.m_Tail = node
	end
end

function clsBaseDLink:pairs()
	local function next(self, preNode)
		--把条件运算符当成三元运算符使用，可能造成死循环
		--node = node and node.Next or self.m_Header
		local node
		if preNode then
			node = preNode.Next
		else
			node = self.m_Header
		end
		if node and node.Data then
			return node, node.Data
		end
	end
	return next, self, nil
end


-- 双向链表类
clsDLink = clsObject:Inherit("clsDLink")

function clsDLink:OnCreate(name)
	Super(clsDLink).OnCreate(self)
	self.m_Name = name
	self:Reset()
end

function clsDLink:OnDestroy()
	Super(clsDLink).OnDestroy(self)
	self:Reset()
end

function clsDLink:Reset()
	self.m_Header = nil
	self.m_Tail = nil
	self.m_Count = 0
	self.m_AllNode = {}
end

-- 插入表尾
function clsDLink:Push(data)
	local node = {Data = data}

	return self:AddNodeToTail(node)
end

-- 删除表头
function clsDLink:Pull()
	local node = self.m_Header
	if node then
		self.m_Header = node.Next
        if self.m_Header then
            self.m_Header.Pre = nil
        else
            -- 队列已经空了
            self.m_Tail = nil
        end
		node.Next = nil
		node.Pre = nil
		self.m_Count = self.m_Count - 1
		self.m_AllNode[node] = nil
	end
	return node and node.Data
end

--增加节点到头部
function clsDLink:AddNodeToHead(node)
	node.Next = nil
	node.Pre = nil
	if not self.m_Header then
		self.m_Header = node
	end
	if not self.m_Tail then
		self.m_Tail = node
	else
		self.m_Header.Pre = node
		node.Next = self.m_Header
		self.m_Header = node
	end
	self.m_Header.Pre = nil
	self.m_AllNode[node] = true
	self.m_Count = self.m_Count + 1
	if IS_TEST_SERVER then
		self:HasCycle()
	end
	return node
end

--增加节点到尾部
function clsDLink:AddNodeToTail(node)
	node.Next = nil
	node.Pre = nil
	if not self.m_Header then
		self.m_Header = node
	end
	if not self.m_Tail then
		self.m_Tail = node
	else
		self.m_Tail.Next = node
		node.Pre = self.m_Tail
		self.m_Tail = node
	end
	self.m_Tail.Next = nil
	self.m_AllNode[node] = true
	self.m_Count = self.m_Count + 1
	if IS_TEST_SERVER then
		self:HasCycle()
	end
	return node
end

-- 删除某个节点
function clsDLink:Remove(node)
	if not self.m_AllNode[node] then return end
	local preNode = node.Pre
	local nextNode = node.Next
	if not preNode then
		-- 表示是链头
		self.m_Header = nextNode
	else
		preNode.Next = nextNode
	end	
	if not nextNode then
		-- 表示是尾部
		self.m_Tail = preNode
	else
		nextNode.Pre = preNode
	end

	--解除前驱与后继的引用
	--暂时不解除  太多地方 pairs边remove 不然会导致遍历不下去
	-- node.Next = nil
	-- node.Pre = nil

	self.m_Count = self.m_Count - 1
	self.m_AllNode[node] = nil
end

--将节点移动到队尾
function clsDLink:MoveToTail(node)
	assert(node)
    -- 不存在的节点，直接返回
    if not self.m_AllNode[node] then return end

    --如果是尾节点 无须移动
	if node == self.m_Tail then return end

	self:Remove(node)
	self:AddNodeToTail(node)
end

--将节点移动到头部
function clsDLink:MoveToHead(node)
	assert(node)
	if not self.m_AllNode[node] then return end

	--是头部
	if node == self.m_Header then return end

	self:Remove(node)
	self:AddNodeToHead(node)
end


function clsDLink:Size()
	return self.m_Count
end

function clsDLink:Empty()
	return self.m_Count == 0
end

function clsDLink:Head()
	return self.m_Header and self.m_Header.Data
end

function clsDLink:Tail()
	return self.m_Tail and self.m_Tail.Data
end

function clsDLink:pairs()
	local function next(self, node)
		--把条件运算符当成三元运算符使用，必定死循环
		-- node = node and node.Next or self.m_Header
		if not node then
			node = self.m_Header
		else
			node = node.Next
		end

		return node,node and node.Data
	end
	return next, self, nil
end

function clsDLink:ToString()
	return string.format("Count=%d", self.m_Count or 0)
end

function clsDLink:HasCycle()
	if not self.m_Header then return end
	if not self.m_Header.Next then return end

	local fast = self.m_Header
	local slow = self.m_Header

	while fast do
		fast = fast.Next
		slow = slow.Next

		if fast then
			fast = fast.Next
		end
		if fast == slow then
			-- debug.printx("链表中有环,请检查")
			assert(false,"链表中有环,请检查")
			-- return true
		end
	end

	return false
end



-- 缓存LRU释放管理
-- 本结构会自行管理缓存，不需要额外处理缓存数据
clsLruCache = clsObject:Inherit("clsLruCache")

function clsLruCache:OnCreate(name, oci)
	self.m_Name = name
	self.m_List = clsDLink:New()
	self.m_List:OnCreate()
	self.m_AllCache = {}
	self.m_ExpireTimeInit = oci and oci.ExpireTimeInit or 0 -- 过期时间的初始值
	self.m_ExpireTimeStep = oci and oci.ExpireTimeStep or 0 -- 过期时间的递减值
	self.m_ExpireTimeMin = oci and oci.ExpireTimeMin or 0
	self.m_ExpireCheckStart = oci and oci.ExpireCheckStart or 0 -- 过期时间递减的判断值
	self.m_ExpireCheckStep = oci and oci.ExpireCheckStep or 0
	self.m_ExpireClearCount = oci and oci.ExpireClearCount or 0 -- 单次清理的最大数量
	self.m_CacheMin = oci and oci.CacheMin or 0 -- 缓存最小数量，不足时完全不释放
	self.m_CacheMax = oci and oci.CacheMax or 0 -- 缓存最大数量，超过时立即释放旧缓存
end

function clsLruCache:GetName()
	return self.m_Name
end

function clsLruCache:SetCapacity(cacheMin, cacheMax)
	self.m_CacheMin = cacheMin or 0
	self.m_CacheMax = cacheMax or 0
	if self.m_CacheMax > 0 then
		while self.m_List:Size() > self.m_CacheMax do
			local uid = self.m_List:Pull()
			self.m_AllCache[uid] = nil
		end
	end
end

--设置缓存释放规则
--默认过期时间为 timeInit，当缓存数量超过 checkStart时，对过期时间进行递减，来加快释放
--缓存数量每达到 checkStep，就递减 timeStep，但是过期时间不得小于 timeMin
function clsLruCache:SetExpireRule(timeInit, timeStep, timeMin, checkStart, checkStep, clearCount)
	if timeInit then self.m_ExpireTimeInit = timeInit end
	if timeStep then self.m_ExpireTimeStep = timeStep end
	if timeMin then self.m_ExpireTimeMin = timeMin end
	if checkStart then self.m_ExpireCheckStart = checkStart end
	if checkStep then self.m_ExpireCheckStep = checkStep end
	if clearCount then self.m_ExpireClearCount = clearCount end
end

function clsLruCache:Size()
	return self.m_List:Size()
end

-- Data 可以为空
function clsLruCache:AddCache(uid, data)
	local cache = self.m_AllCache[uid]
	if cache then
		cache.Data = data
		self.m_List:MoveToTail(cache.Node)
		return
	end

	if self.m_CacheMax and self.m_CacheMax > 0 and self.m_List:Size() >= self.m_CacheMax then
		local oldUid = self.m_List:Pull()
		self.m_AllCache[oldUid] = nil
	end

	self.m_AllCache[uid] = {
		Data = data,
		Node = self.m_List:Push(uid),
		Time = os_time(),
	}
end

function clsLruCache:GetCache(uid)
	local cache = self.m_AllCache[uid]
	if not cache then return false end
	self.m_List:MoveToTail(cache.Node)
	cache.Time = os_time()
	return true, cache.Data
end

function clsLruCache:RemoveCache(uid)
	local cache = self.m_AllCache[uid]
	if not cache then return end
	self.m_List:Remove(cache.Node)
	self.m_AllCache[uid] = nil
	return cache.Data
end

function clsLruCache:ExpireCache(expireList, now, expireTime, clearCount)
	local size = self.m_List:Size()
	if self.m_CacheMin and self.m_CacheMin > 0 and size <= self.m_CacheMin then
		return
	end

	if not expireTime then
		expireTime = self.m_ExpireTimeInit
		if self.m_ExpireCheckStart and self.m_ExpireCheckStart > 0 and size >= self.m_ExpireCheckStart and self.m_ExpireCheckStep > 0 then
			expireTime = expireTime - size * self.m_ExpireTimeStep / self.m_ExpireCheckStep
			if self.m_ExpireTimeMin and expireTime < self.m_ExpireTimeMin then
				expireTime = self.m_ExpireTimeMin
			end
		end
	end

	now = now or os_time()
	local lastTime = now - expireTime
	local count = 0
	clearCount = clearCount or self.m_ExpireClearCount
	-- local expireNodeList = {}
	for node, uid in self.m_List:pairs() do
		local cache = self.m_AllCache[uid]
		if cache.Time > lastTime then break end
		self.m_List:Remove(node)
		self.m_AllCache[uid] = nil
		-- expireNodeList[uid] = node
		if expireList then
			expireList[uid] = cache.Data or true
		end
		count = count + 1
		if clearCount and count >= clearCount then break end
	end
	
	-- for uid,node in pairs(expireNodeList or {}) do
	-- 	local cache = self.m_AllCache[uid]
	-- 	if cache then
	-- 		self.m_List:Remove(node)
	-- 		self.m_AllCache[uid] = nil
	-- 	end
	-- end

	return count
end

function clsLruCache:GetAllCache()
	local allCache = {}
	for uid, cache in pairs(self.m_AllCache) do
		allCache[uid] = cache.Data
	end
	return allCache
end

function clsLruCache:pairs()
	local function customerNext(self, preUid)
		local uid, cache = next(self.m_AllCache, preUid)
		if uid then
			return uid, cache.Data
		end
	end
	return customerNext, self, nil
end

function clsLruCache:Clear()
	self.m_List:Reset()
	self.m_AllCache = {}
end






--更轻更高效的LRU缓存管理 leetcode 146题
--注意：这是唯一链表，节点内容不能重复
--建议不要把对象或数据直接放入缓存管理，可以放对象或数据的Key，比如玩家Uid，联盟Id
clsLruCacheLite = clsObject:Inherit("clsLruCacheLite")
function clsLruCacheLite:OnCreate(name, oci)
	self.m_Name = name
    self.m_Size = 0
    self.m_Header = nil
    self.m_Tail = nil
	self.m_AllNode = {}
	self.m_ExpireTimeInit = oci and oci.ExpireTimeInit -- 过期时间的初始值
	self.m_ExpireTimeStep = oci and oci.ExpireTimeStep -- 过期时间的递减值
	self.m_ExpireTimeMin = oci and oci.ExpireTimeMin
	self.m_ExpireCheckStart = oci and oci.ExpireCheckStart -- 过期时间递减的判断值
	self.m_ExpireCheckStep = oci and oci.ExpireCheckStep
	self.m_ExpireClearCount = oci and oci.ExpireClearCount -- 单次清理的最大数量
end

function clsLruCacheLite:ToString()
	return string.format("Name=%s", tostring(self.m_Name))
end

--设置缓存释放规则
--默认过期时间为 timeInit，当缓存数量超过 checkStart时，对过期时间进行递减，来加快释放
--缓存数量每达到 checkStep，就递减 timeStep，但是过期时间不得小于 timeMin
function clsLruCacheLite:SetExpireRule(timeInit, timeStep, timeMin, checkStart, checkStep, clearCount)
	if timeInit then self.m_ExpireTimeInit = timeInit end
	if timeStep then self.m_ExpireTimeStep = timeStep end
	if timeMin then self.m_ExpireTimeMin = timeMin end
	if checkStart then self.m_ExpireCheckStart = checkStart end
	if checkStep then self.m_ExpireCheckStep = checkStep end
	if clearCount then self.m_ExpireClearCount = clearCount end
end

function clsLruCacheLite:Clear()
	self.m_Size = 0
    self.m_Header = nil
    self.m_Tail = nil
	self.m_AllNode = {}
end

function clsLruCacheLite:Push(data)
    if not data then return false end
    if self.m_AllNode[data] then return false end

    local node = {
        Time = os_time(),
        Data = data,
        Last = nil,
        Next = nil,
    }

    if not self.m_Header then
        self.m_Header = node
    end
    if self.m_Tail then
        local lastNode = self.m_Tail
        lastNode.Next = node
        node.Last = lastNode
    end

    self.m_Tail = node
    self.m_Size = self.m_Size + 1
    self.m_AllNode[data] = node
    return true
end

function clsLruCacheLite:Pop()
    local headerNode = self.m_Header
    if not headerNode then return end

    local data = headerNode.Data
    local nextNode = headerNode.Next
    self.m_Header = nextNode

    if nextNode then
        nextNode.Last = nil
	else
		--NextNode不存在，表示最后一个节点也被删除
        self.m_Tail = nil
    end

    self.m_Size = self.m_Size - 1
    self.m_AllNode[data] = nil
    return data
end

function clsLruCacheLite:Pick(data)
    local node = self.m_AllNode[data]
    if not node then return false end

    local lastNode = node.Last
    local nextNode = node.Next

    if lastNode then
        lastNode.Next = nextNode
    else
        self.m_Header = nextNode
    end

    if nextNode then
        nextNode.Last = lastNode
    else
        self.m_Tail = lastNode
    end

    self.m_Size = self.m_Size - 1
    self.m_AllNode[data] = nil
    return true
end

function clsLruCacheLite:Refresh(data, now)
    local node = self.m_AllNode[data]
    if not node then return end

	now = now or os_time()
    node.Time = now

    local tailNode = self.m_Tail
    if node == tailNode then return end     --原本就在队尾，无需处理

    local lastNode = node.Last
    local nextNode = node.Next

    --lastNode存在，说明Node不在队头
    if lastNode then
        lastNode.Next = nextNode
    else
        self.m_Header = nextNode
    end
    nextNode.Last = lastNode

    tailNode.Next = node
    node.Last = tailNode
    node.Next = nil
    self.m_Tail = node
end

function clsLruCacheLite:RefreshList(dataList)
    local now = os_time()
    for _, data in ipairs(dataList) do
        self:Refresh(data, now)
    end
end

--注意，ExpireList是一个数组
function clsLruCacheLite:ExpireCache(expireList, now, expireTime, clearCount)
	if not expireTime then
		expireTime = self.m_ExpireTimeInit
		local size = self.m_Size
		if self.m_ExpireCheckStart and self.m_ExpireCheckStart > 0 and size >= self.m_ExpireCheckStart and self.m_ExpireCheckStep > 0 then
			expireTime = expireTime - size * self.m_ExpireTimeStep / self.m_ExpireCheckStep
			if self.m_ExpireTimeMin and expireTime < self.m_ExpireTimeMin then
				expireTime = self.m_ExpireTimeMin
			end
		end
	end
	local size = #expireList
	clearCount = clearCount or self.m_ExpireClearCount or 0
	now = now or os_time()
	local lastTime = now - expireTime
    while self.m_Header and (clearCount <= 0 or size < clearCount) do
		local tm = self.m_Header.Time
		if tm > lastTime then break end
		--刷新时间在到期时间之前的节点，都已超时
		local data = self:Pop()
		size = size + 1
        expireList[size] = data
    end
    return size
end

function clsLruCacheLite:Size()
    return self.m_Size
end

function clsLruCacheLite:Print()
    local node = self.m_Header
    print(self.m_Header)
    while node do
        local data = node.Data
        print(data, node.Last, node, node.Next)
        node = node.Next
    end
    print(self.m_Tail)
end



-- 考虑到位操作的有效性，每个数值最大只允许设置到50bit，而引擎层传递协议的时候为了安全，只允许48bit
local BIT_VALID_LEN = 48

clsBits = ALL_CLASS.clsCoreObj:Inherit("clsBits")

function clsBits:__init__()
	Super(clsBits).__init__(self)
	self.m_Value = 0
end

function clsBits:GetValue()
	return self.m_Value
end

function clsBits:SetValue(value)
	self.m_Value = value
end

function clsBits:On(pos)
	assert(pos >=0 and pos <= BIT_VALID_LEN)
	if ll_get_bit(self.m_Value, pos) then return false end
	self.m_Value = ll_set_bit(self.m_Value, pos, 1)
	return true
end

function clsBits:Off(pos)
	assert(pos >=0 and pos <= BIT_VALID_LEN)
	if not ll_get_bit(self.m_Value, pos) then return false end
	self.m_Value = ll_set_bit(self.m_Value, pos, 0)
	return true
end

-- is on
function clsBits:IsOn(pos)
	assert(pos >=0 and pos <= BIT_VALID_LEN)
	return ll_get_bit(self.m_Value, pos)
end



--------------------------------------------------------------------------------
-- 位图类，本质是一个long-long的数组，方便和存盘对接
--------------------------------------------------------------------------------
clsBitMap = ALL_CLASS.clsCoreObj:Inherit("clsBitMap")

function Key2Idx(key)
	local pos = math_floor(key / BIT_VALID_LEN) + 1
	local idx = key - (pos - 1) * BIT_VALID_LEN
	return pos, idx
end

function Idx2Key(pos, idx)
	return idx + (pos - 1) * BIT_VALID_LEN
end

function clsBitMap:__init__()
	Super(clsBitMap).__init__(self)
	self.m_Values = {}
end

function clsBitMap:Load(values)
	-- local values = XEngine.unpack(str)
	-- assert(values and type(values) == "table")
	self.m_Values = values
end

function clsBitMap:Dump()
	-- return XEngine.pack(self.m_Values)
	return self.m_Values
end

function clsBitMap:On(key)
	local pos, idx = Key2Idx(key)
	local value = self.m_Values[pos] or 0
	value = ll_set_bit(value, idx, 1)
	self.m_Values[pos] = value
	return pos, value
end

function clsBitMap:Off(key)
	local pos, idx = Key2Idx(key)
	local value = self.m_Values[pos]
	if (not value) or value == 0 then return end
	value = ll_set_bit(value, idx, 0)
	if value == 0 then
		self.m_Values[pos] = nil
	else
		self.m_Values[pos] = value
	end
	return pos, value
end

function clsBitMap:IsOn(key)
	local pos, idx = Key2Idx(key)
	local value = self.m_Values[pos]
	if (not value) or value == 0 then return false end
	return ll_get_bit(value, idx)
end

function clsBitMap:GetAllKey()
	local keys = {}
	local start
	for pos, value in pairs(self.m_Values) do
		start = (pos - 1) * BIT_VALID_LEN
		for idx = 0, BIT_VALID_LEN do
			if ll_get_bit(value, idx) then
				table.insert(keys, start + idx)
			end
		end
	end
	return keys
end

-- 另外一种封装方式，目的是不用class，方便碎片存盘
function BitMapOn(values, key)
	local pos, idx = Key2Idx(key)
	local value = values[pos] or 0
	value = ll_set_bit(value, idx, 1)
	values[pos] = value
	return pos
end

function BitMapOff(values, key)
	local pos, idx = Key2Idx(key)
	local value = values[pos]
	if (not value) or value == 0 then return end
	value = ll_set_bit(value, idx, 0)
	if value == 0 then
		values[pos] = nil
	else
		values[pos] = value
	end
	return pos
end

function BitMapIsOn(values, key)
	if (not values) or (not next(values)) then return false end
	local pos, idx = Key2Idx(key)
	local value = values[pos]
	if (not value) or value == 0 then return false end
	return ll_get_bit(value, idx)
end

-- 取出第一个key
function BitMapFirstKey(values)
	if (not values) or (not next(values)) then return end
	local minKey, minValue
	for k, v in pairs(values) do
		if (not minKey) or k < minKey then
			minKey = k
			minValue = v
		end
	end
	if (not minKey) or (not minValue) then return end
	local idx = bit.ll_first(minValue) or 0
	if idx < 1 then return end
	return idx + (minKey - 1) * BIT_VALID_LEN
end

function BitMapKeyList(values)
	if (not values) or (not next(values)) then return end
	local keys = {}
	local start
	local cnt = 0
	for pos, value in pairs(values) do
		start = (pos - 1) * BIT_VALID_LEN
		for idx = 0, BIT_VALID_LEN do
			if ll_get_bit(value, idx) then
				cnt = cnt + 1
				keys[cnt] = start + idx
			end
		end
	end
	return keys
end

_G.BitMapOn = BitMapOn
_G.BitMapOff = BitMapOff
_G.BitMapIsOn = BitMapIsOn
_G.BitMapFirstKey = BitMapFirstKey
_G.BitMapKeyList = BitMapKeyList



--------------------------------------------------------------------------------
-- 玩家uid集合类，按照uid的规则写入到bitmap中，减少内存和序列化占用
--------------------------------------------------------------------------------
-- m_BitMaps = {
-- 	[group] = {
-- 		[pos] = number,
-- 	}
-- }

clsUidSet = ALL_CLASS.clsCoreObj:Inherit("clsUidSet")

function clsUidSet:__init__()
	Super(clsUidSet).__init__(self)
	self.m_Values = {}
end

function clsUidSet:Load(values)
	-- local values = XEngine.unpack(str)
	-- assert(values and type(values) == "table")
	self.m_Values = values
end

function clsUidSet:Dump()
	-- return XEngine.pack(self.m_Values)
	return self.m_Values
end

-- uid的低7位分别是hostid和gsid
function clsUidSet:Key2Idx(key)
	local low = key % 10000000
	local high = math_floor(key / 10000000)
	local pos = math_floor(high / BIT_VALID_LEN) + 1
	local idx = high - (pos - 1) * BIT_VALID_LEN
	return low, pos, idx
end

function clsUidSet:On(key)
	local group, pos, idx = self:Key2Idx(key)
	local valueList = self.m_Values[group]
	if not valueList then
		valueList = {}
		self.m_Values[group] = valueList
	end
	local value = valueList[pos] or 0
	value = ll_set_bit(value, idx, 1)
	valueList[pos] = value
	return group, pos, value
end

function clsUidSet:Off(key)
	local group, pos, idx = self:Key2Idx(key)
	local valueList = self.m_Values[group]
	if (not valueList) or (not next(valueList)) then return end
	local value = valueList[pos]
	if (not value) or value == 0 then return end
	value = ll_set_bit(value, idx, 0)
	valueList[pos] = value
	return group, pos, value
end

function clsUidSet:IsOn(key)
	local group, pos, idx = self:Key2Idx(key)
	local valueList = self.m_Values[group]
	if (not valueList) or (not next(valueList)) then return false end
	local value = valueList[pos]
	if (not value) or value == 0 then return false end
	return ll_get_bit(value, idx)
end

-- 另外一种封装方式，目的是不用class，方便碎片存盘
-- uid的低7位分别是hostid和gsid
local function Uid2Idx(uid)
	local low = uid % 10000000
	local high = math_floor(uid / 10000000)
	local pos = math_floor(high / BIT_VALID_LEN) + 1
	local idx = high - (pos - 1) * BIT_VALID_LEN
	return low, pos, idx
end

function UidBitMapOn(values, uid)
	local hostid, pos, idx = Uid2Idx(uid)
	local hostinfo = values[hostid] or {}
	local value = hostinfo[pos] or 0
	value = ll_set_bit(value, idx, 1)
	hostinfo[pos] = value
	values[hostid] = hostinfo
	return pos
end

function UidBitMapOff(values, uid)
	local hostid, pos, idx = Uid2Idx(uid)
	local hostinfo = values[hostid]
	if not hostinfo then return end
	local value = hostinfo[pos] or 0
	if (not value) or value == 0 then return end
	value = ll_set_bit(value, idx, 0)
	if value == 0 then
		hostinfo[pos] = nil
	else
		hostinfo[pos] = value
	end
	return pos
end

function UidBitMapIsOn(values, uid)
	if (not values) or (not next(values)) then return false end
	local hostid, pos, idx = Uid2Idx(uid)
	local hostinfo = values[hostid]
	if not hostinfo then return false end
	local value = hostinfo[pos]
	if (not value) or value == 0 then return false end
	return ll_get_bit(value, idx)
end

function UidBitMapFirstKey(values)
	if (not values) or (not next(values)) then return end
	local minHost, minKey, minValue
	for host, list in pairs(values) do
		for k, v in pairs(list) do
			if (not minKey) or (not minHost) or k < minKey then
				minHost = host
				minKey = k
				minValue = v
			end
		end
	end
	if (not minHost) or (not minKey) or (not minValue) then return end
	local idx = bit.ll_first(minValue) or 0
	if idx < 1 then return end
	return (idx + (minKey - 1) * BIT_VALID_LEN) * 10000000 + minHost
end

function UidBitMapKeyList(values)
	if (not values) or (not next(values)) then return end
	local keys = {}
	local cnt = 0
	local start
	for host, list in pairs(values) do
		for pos, value in pairs(list) do
			start = (pos - 1) * BIT_VALID_LEN
			for idx = 0, BIT_VALID_LEN do
				if ll_get_bit(value, idx) then
					cnt = cnt + 1
					keys[cnt] = (start + idx) * 10000000 + host
				end
			end
		end
	end
	return keys
end

_G.UidBitMapOn			= UidBitMapOn
_G.UidBitMapOff			= UidBitMapOff
_G.UidBitMapIsOn		= UidBitMapIsOn
_G.UidBitMapFirstKey	= UidBitMapFirstKey
_G.UidBitMapKeyList		= UidBitMapKeyList




-- 双向链表 + 桶
-- 桶内 是双向链表的数据结构
-- 桶与桶之间也是双向链表
clsBucket = clsObject:Inherit("clsBucket")
function clsBucket:OnCreate()
	Super(clsBucket).OnCreate(self)
	self.m_Count = 0
    self.m_CreateTime = os_time() --桶创建时间
	self:Reset()
end

function clsBucket:Reset()
	self.m_Header = nil --桶的头节点
	self.m_Tail = nil --桶的尾节点
	self.m_LastBucket = nil --前一个桶
	self.m_NextBucket = nil --后一个桶
end

function clsBucket:GetBucketTailNode()
	return self.m_Tail
end

function clsBucket:GetBucketHeaderNode()
	return self.m_Header
end

--将节点加到桶的头部
function clsBucket:AddNodeToBucketHeader(newNode)
	--debug.printx("AddNodeToBucketHeader:",newNode.Id)
	if not self.m_Header then
		self.m_Header = newNode
		self.m_Tail = newNode
	else
		newNode.Down = self.m_Header
		self.m_Header.Up = newNode
		self.m_Header = newNode
	end
	self.m_Count = self.m_Count + 1
	--debug.printx("count:",self.m_Count)
	--self:Traverse()
end

--判断这个桶是否为空
function clsBucket:IsEmpty()
	return not self.m_Header
end

--删除node
function clsBucket:DeleteBucketNode(node)
	--debug.printx("DeleteBucketNode",node.Times,self.m_Count)
	--self:Traverse()
	if self.m_Tail == self.m_Header then
		self.m_Tail = nil
		self.m_Header = nil
	else
		if node == self.m_Header then
			self.m_Header = node.Down
			self.m_Header.Up = nil
		elseif node == self.m_Tail then
			self.m_Tail = node.Up
			self.m_Tail.Down = nil
		else
			node.Up.Down = node.Down
			node.Down.Up = node.Up
		end
	end
	node.Up = nil
	node.Down = nil
	self.m_Count = self.m_Count - 1
	assert(self.m_Count >= 0)
	--debug.printx("DeleteBucketNode",self.m_Tail,self.m_Header,self.m_Count)
	--self:Traverse()
end

function clsBucket:DeleteBucketTailNode()
	if self.m_Header then
		self:DeleteBucketNode(self.m_Header)
	end
end


--清空桶内节点
function clsBucket:ClearBucketNode()

end

function clsBucket:pairs()
	--local header = self.m_Header
    local function next(self, preNode)
        local node
        if preNode then
            node = preNode.Down
        else
            node = self.m_Header
        end
        if node then
			debug.printx(node.Id,node.Times)
            return node, node
        end
    end
    return next, self, nil
end

--遍历
function clsBucket:Traverse()
	local header = self:GetBucketHeaderNode()
	while header do
		debug.printx(header.Id,header.Times)
		header = header.Down
	end
end

function clsBucket:OnDestroy()
	Super(clsBucket).OnDestroy(self)
	self:Reset()
end


--LFU 缓存类 leetcode 460题
--LFU主要是淘汰最近使用次数最少的元素，当使用次数相同时，再使用LRU策略进行淘汰。
clsLfuCache = clsObject:Inherit("clsLfuCache")
function clsLfuCache:OnCreate()
    Super(clsLfuCache).OnCreate(self)

    self.m_Capacity = 100 --缓存大小限制
    self.m_Size = 0 --缓存目前有多少节点
    self.m_Id2Node = {} --所有节点的哈希表
    self.m_Node2Bucket = {} -- 节点在哪个桶里

    self.m_LeftBucket = nil --最左的桶
end


function clsLfuCache:AddCache(id,cache)
    assert(id and cache)
	if self.m_Capacity == 0 then return end

	if self.m_Id2Node[id] then
		local node = self.m_Id2Node[id]
		node.Data = cache
		node.Times = node.Times + 1
		local bucket = self.m_Node2Bucket[node]
		self:Move(node,bucket)
	else
		if self.m_Size == self.m_Capacity then
			local node = self.m_LeftBucket:GetBucketTailNode()
			self.m_LeftBucket:DeleteBucketNode(node)
			self.m_Id2Node[node.Id] = nil
			self.m_Node2Bucket[node] = nil
			self.m_Size = self.m_Size - 1
		end
		local node = {
			Id = id,
			Data = cache,
			Times = 1,
		}
		if not self.m_LeftBucket then
			self.m_LeftBucket = clsBucket:New()
			self.m_LeftBucket:OnCreate()
			self.m_LeftBucket:AddNodeToBucketHeader(node)

			assert(self.m_LeftBucket)
		else
            if self.m_LeftBucket.m_Header.Times == node.Times then
                self.m_LeftBucket:AddNodeToBucketHeader(node)
            else
                local bucket = clsBucket:New()
                bucket:OnCreate()
                bucket:AddNodeToBucketHeader(node)
                bucket.m_NextBucket = self.m_LeftBucket
                self.m_LeftBucket.m_LastBucket = bucket
                self.m_LeftBucket = bucket
				assert(self.m_LeftBucket)
            end
		end
        self.m_Id2Node[id] = node
        self.m_Node2Bucket[node] = self.m_LeftBucket
        self.m_Size = self.m_Size + 1
    end
end


function clsLfuCache:GetCache(id)
    local node = self.m_Id2Node[id]
    if not node then return end

	if node.Times ~= 0xfffffff then
		node.Times = node.Times + 1
	end
    local bucket = self.m_Node2Bucket[node]
    self:Move(node,bucket)
    return node.Data
end

--内部调用
--减少只有一个节点的桶
function clsLfuCache:ModifyBucket(removeBucket)
    if removeBucket:IsEmpty() then
        if self.m_LeftBucket == removeBucket then
            self.m_LeftBucket = removeBucket.m_NextBucket
            if self.m_LeftBucket then
                self.m_LeftBucket.m_LastBucket = nil
            end
        else
            removeBucket.m_LastBucket.m_NextBucket = removeBucket.m_NextBucket
            if removeBucket.m_NextBucket then
                removeBucket.m_NextBucket.m_LastBucket = removeBucket.m_LastBucket
            end
        end
        return true
    end
    return false
end

--内部调用
function clsLfuCache:Move(node,oldBucket)
	oldBucket:DeleteBucketNode(node)
    --preBucket 表示次数 + 1的桶的前一个桶是谁
    local isSuccess = self:ModifyBucket(oldBucket)
    local preBucket = isSuccess and oldBucket.m_LastBucket or oldBucket
    --nextBucket 表示次数+1的桶的后一个桶
    local nextBucket = oldBucket.m_NextBucket
    if isSuccess then
        oldBucket:OnDestroy()
    end
    if not nextBucket then
        local newBucket = clsBucket:New()
        newBucket:OnCreate()
        newBucket:AddNodeToBucketHeader(node)
        if preBucket then
            preBucket.m_NextBucket = newBucket
        end
        newBucket.m_LastBucket = preBucket
        if not self.m_LeftBucket then
            self.m_LeftBucket = newBucket
			assert(self.m_LeftBucket)
        end
        self.m_Node2Bucket[node] = newBucket
    else
        if nextBucket.m_Header.Times == node.Times then
            nextBucket:AddNodeToBucketHeader(node)
            self.m_Node2Bucket[node] = nextBucket
        else
            local newBucket = clsBucket:New()
            newBucket:OnCreate()
            newBucket:AddNodeToBucketHeader(node)
            if preBucket then
                preBucket.m_NextBucket = newBucket
            end
            newBucket.m_LastBucket = preBucket
            newBucket.m_NextBucket = nextBucket
            nextBucket.m_LastBucket = newBucket
            if self.m_LeftBucket == nextBucket then
                self.m_LeftBucket = newBucket
				assert(self.m_LeftBucket)
            end
            self.m_Node2Bucket[node] = newBucket
        end
    end
	assert(self.m_LeftBucket)
end

--清除桶内所有节点
function clsLfuCache:ClearBucketNode(bucket)
	local headerNode = bucket.m_Header
	local tailNode = bucket.m_Tail

	while headerNode do
		assert(headerNode.Bucket == bucket)
		headerNode.Bucket = nil
		self.m_Id2Node[headerNode.Id] = nil
        self.m_Node2Bucket[headerNode] = nil
		if headerNode == tailNode then
			headerNode = nil
			tailNode = nil
		else
			local preNode = headerNode.Pre
			preNode.Next = nil
			headerNode.Pre = nil
			headerNode = preNode
		end
	end
end

function clsLfuCache:RemoveCache(id)
    local node = self.m_Id2Node[id]
    if not node then return end

	local bucket = self.m_Node2Bucket[node]
	bucket:DeleteBucketNode(node)
	local isSuccess = self:ModifyBucket(bucket) --桶空了
	if isSuccess then
		bucket:OnDestroy()
	end

	self.m_Id2Node[id] = nil
	self.m_Size = self.m_Size - 1
	self.m_Node2Bucket[node] = nil
end

--过期规则
function clsLfuCache:ExpireCache()
	--self:pairs()
	--自行扩展
end

function clsLfuCache:pairs()
	debug.printx("pairs start")
	debug.printx("总数量 size:",self:Size())
	local total = 0
	for _,bucket in self:pairs() do
		total = total + bucket.m_Count
		debug.printx("桶内节点数量:",bucket.m_Count)
		for _,Data in bucket:pairs() do
			--debug.printx("cache:",Data.Id,Data.Times)
		end
	end
	assert(total == self:Size())
	debug.printx("pairs end")
end

function clsLfuCache:Traverse()
	local leftBucket = self.m_LeftBucket
	while leftBucket do
		leftBucket:Traverse()
		leftBucket = leftBucket.m_NextBucket
	end
end

function clsLfuCache:Size()
    return self.m_Size
end

--移除过期的桶
function clsLfuCache:RemoveExpireBucket()

end

function clsLfuCache:pairs()
	local leftBucket = self.m_LeftBucket
	local function next(self, preBucket)
		local bucket
		if preBucket then
			bucket = preBucket.m_NextBucket
		else
			bucket = leftBucket
		end
		if bucket then
			return bucket,bucket
		end
	end
	return next, self, nil
end



-- 堆
-- 目前最常见的用法：将一组key push到heap中，维持第一个元素是最小或者最大

local function Swap(list, a, b)
	if a == b then return end
	local tmp = list[a]
	list[a] = list[b]
	list[b] = tmp
end

local function DEFAULT_SORT_FUNC(a, b)
	return a > b
end

--把堆想象成一颗完全二叉树,那么有以下结论
--如果 当前节点的下标索引是 index, 
--那么父节点下标索引是 math.floor(index / 2) , 左孩子是 2*index 右孩子是 2*index + 1
clsHeap = clsObject:Inherit("clsHeap")
function clsHeap:OnCreate(size, func)
    Super(clsHeap).OnCreate(self)
	self.m_MaxSize = size or 0
	self.m_CurSize = 0
	self.m_SortFunc = func or DEFAULT_SORT_FUNC --排序func
	self.m_List = {}
end

function clsHeap:IsEmpty()
	return self.m_CurSize == 0
end

function clsHeap:IsFull()
	if self.m_MaxSize <= 0 then return false end
	return self.m_CurSize >= self.m_MaxSize
end

function clsHeap:Clear()
	self.m_CurSize = 0
	self.m_List = {}
end

function clsHeap:Reset(array)
	self.m_CurSize = 0
	self.m_List = {}
	for _, v in ipairs(array) do
		self:Push(v)
	end
end

function clsHeap:Remove(value)
	if self.m_CurSize == 0 then return end
	local index
	for k, v in ipairs(self.m_List) do
		if v == value then
			index = k
			break
		end
	end
	if not index then return end
	--将数组最后一个元素
	if index ~= self.m_CurSize then
		Swap(self.m_List, index, self.m_CurSize)
	end
	self.m_List[self.m_CurSize] = nil
	self.m_CurSize = self.m_CurSize - 1
	self:Heapify(index)
end

function clsHeap:Push(value)
	-- printx("Push:", value)
	if self.m_MaxSize > 0 and self.m_CurSize >= self.m_MaxSize then
		return
	end

	self.m_CurSize = self.m_CurSize + 1
	self.m_List[self.m_CurSize] = value
	self:HeapInsert(self.m_CurSize)
end

function clsHeap:Pop()
	if self.m_CurSize == 0 then return end
	local tmp = self.m_List[1]
	-- printx("temp:",tmp)
	--将数组最后一个元素
	if self.m_CurSize ~= 1 then
		Swap(self.m_List, 1, self.m_CurSize)
	end
	self.m_List[self.m_CurSize] = nil
	self.m_CurSize = self.m_CurSize - 1
	self:Heapify(1)
	return tmp
end

function clsHeap:Head()
	return self.m_List[1]
end

--往上看 与父节点比较
function clsHeap:HeapInsert(index)
	assert(type(index) == "number")
	--如果 index > 0 且 一直大于父节点 那么就一直与父节点交换
	local fatherIndex = math_floor(index / 2)
	while (index > 0 and fatherIndex > 0 and self.m_SortFunc(self.m_List[index], self.m_List[fatherIndex])) do
		Swap(self.m_List, index, fatherIndex)
		index = fatherIndex
		fatherIndex = math_floor(index / 2)
	end
end

--从 index 位置 一直往下
--停止的情形: 我的孩子都不在比我大 或者 已经没有孩子了
function clsHeap:Heapify(index)
	local heapSize = self.m_CurSize
	--左孩子位置
	local left = 2 * index
	while left <= heapSize do
		-- 左右两个孩子中,谁大,谁把自己的下标给largest
		--1.有右孩子 判断左右孩子谁大
		--2.无右孩子 自己左孩子

		local right = left + 1
		local largest = right <= heapSize and (self.m_SortFunc(self.m_List[left],self.m_List[right]) and left or right) or left
		largest = self.m_SortFunc(self.m_List[index], self.m_List[largest]) and index or largest

		--左右孩子都不比父节点大  break
		if largest == index then break end
		Swap(self.m_List, largest, index)
		index = largest
		left = index * 2
	end
end

--更新，某个value发生变化，需要重新排列
function clsHeap:Update(value)
	local pos
	for k, v in ipairs(self.m_List) do
		if v == value then
			pos = k
			break
		end
	end
	if not pos then
		self:Push(value)
	else
		--向下看
		self:HeapInsert(pos)
		--向上看
		self:Heapify(pos)
	end
end

function clsHeap:Dump()
	printx("Dump start")
	for _,v in ipairs(self.m_List) do
		printx(v)
	end
	printx("Dump end")
end

--插入排序 自定义升序func  值分别为 1,0,-1 
--底部有案例
--实现原理 就是 leetcode 34 35 题
--为了实现唯一键更新 所以插入的值必须是一个 table 且内部含有唯一键 代码中默认了 Id = Id
--InsertValue 更新和新值都是同一接口
clsInsertSort = clsObject:Inherit("clsInsertSort")
function clsInsertSort:OnCreate(Size,Func)
    Super(clsInsertSort).OnCreate(self)

	assert(type(Func) == "function")
	assert(type(Size) == "number")

	self.m_Size = Size
	assert(self.m_Size > 0)
	self.m_SortFunc = Func --排序func

	self.m_List = {}
	self.m_Id2Info = {}
end

--内部调用 向左区间找
function clsInsertSort:SearchLeft( Info,L,R )
	local M
	local InsertPos = R
	local Compare
	while L <= R do
		M = L + math.floor((R - L) / 2)
		--只有小于等于的可能
		local Compare = self.m_SortFunc(self.m_List[M],Info)
		if Compare == 0 then
			InsertPos = M
			R = M - 1
		else
			L = M + 1
		end
	end
	return InsertPos
end

--内部调用 向右区间找
function clsInsertSort:SearchRight(Info,L,R)
	local M
	local InsertPos = L
	local Compare

	while L <= R do
		M = L + math.floor((R - L) / 2)
		--只有大于等于的可能
		Compare = self.m_SortFunc(self.m_List[M],Info)
		if Compare == 0 then
			InsertPos = M
			L = M + 1
		else
			R = M - 1
		end
	end

	return InsertPos
end

--内部调用
function clsInsertSort:SearchLeftOrRight(Info,L,Index,R)
	return self:SearchLeft( Info,L,Index ),self:SearchRight(Info,Index,R)
end

--寻找 Info 的插入点或相等区间
function clsInsertSort:FindInsertPosOrRange(Info)
	--先处理特殊情况
	if #self.m_List == 0 then return false,1 end

	local R = #self.m_List
	local L = 1
	local InsertPos = 0
	local M

	while (L <= R) do
		M = L + math.floor((R - L) / 2)

		local Compare = self.m_SortFunc(self.m_List[M],Info)
		if Compare == 1 then --大于 往前排
			R = M - 1
			InsertPos = M
		elseif Compare == -1 then --小于
			L = M + 1
		else --等于
			--找到相等的区间
			local Left,Right = self:SearchLeftOrRight(Info,L,M,R)

			--相等时 默认插到相等区间的最右侧
			return true,Left,Right
		end
	end
	return false,InsertPos == 0 and #self.m_List + 1 or InsertPos
end

--插入一个新值 内部使用
function clsInsertSort:InsertNewValue( Id,NewInfo )
	local len = #self.m_List
	--长度到达限制 且 NewInfo 小于最后一位
	if len >= self.m_Size and self.m_SortFunc(self.m_List[len],NewInfo) then
		return
	end

	local InsertPos
	local IsRange,Left,Right = self:FindInsertPosOrRange(NewInfo)
	if not IsRange then
		InsertPos = Left 
	else
		--是区间 插到区间的最后
		InsertPos = Right + 1
	end

	if InsertPos > len then
		table.insert(self.m_List,NewInfo)
	else
		table.insert(self.m_List,InsertPos,NewInfo)
	end
	self.m_Id2Info[Id] = NewInfo
	NewInfo.Rank = InsertPos
end

--插入数据 对外接口
function clsInsertSort:InsertValue( Id,NewInfo )
	NewInfo.Id = Id --防止没有唯一键的情况
	local OldInfo = self.m_Id2Info[Id]

	--第一次插入
	if not OldInfo then
		self:InsertNewValue( Id,NewInfo )
	else
		local OldRank = OldInfo.Rank

		--先找到它的位置 移除它 再插入新的值
		if self.m_List[OldRank] and self.m_List[OldRank].Id == Id then
			table.remove(self.m_List,OldRank)
			self.m_Id2Info[Id] = nil
			self:InsertNewValue( Id,NewInfo )
		else
			local IsRange,Left,Right = self:FindInsertPosOrRange(OldInfo)
			assert(IsRange)
			for i = Left,Right,1 do
				if self.m_List[i].Id == Id then
					table.remove(self.m_List,i)
					self.m_Id2Info[Id] = nil
					self:InsertNewValue( Id,NewInfo )
					break
				end
			end
		end
	end
	if #self.m_List > self.m_Size then
		table.remove(self.m_List,#self.m_List)
	end
end

--通过Id 查找 在列表中的准备位置
function clsInsertSort:FindRankById(Id)
	local Info = self.m_Id2Info[Id]
	if Info then
		local Rank = Info.Rank
		if self.m_List[Rank] and self.m_List[Rank].Id == Id then
			return Rank
		else
			local IsRange,Left,Right = self:FindInsertPosOrRange(Info)
			assert(IsRange)
			for i = Left,Right,1 do
				if self.m_List[i].Id == Id then
					--重新修正 Rank
					Info.Rank = i
					return i
				end
			end
		end
	end
	return 0
end

--移除
function clsInsertSort:RemoveValueById(Id)
	local OldInfo = self.m_Id2Info[Id]
	if OldInfo then
		local OldRank = OldInfo.Rank
		self.m_Id2Info[Id] = nil
		--先找到它的位置 移除它 再插入新的值
		if self.m_List[OldRank] and self.m_List[OldRank].Id == Id then
			-- debug.printx("移除成功:",Id)
			table.remove(self.m_List,OldRank)
		else
			local IsRange,Left,Right = self:FindInsertPosOrRange(OldInfo)
			assert(IsRange)
			for i = Left,Right,1 do
				if self.m_List[i].Id == Id then
					-- debug.printx("移除成功:",Id)
					table.remove(self.m_List,i)
					break
				end
			end
		end
	end
end

--遍历
function clsInsertSort:Traverse()
	for _,Info in ipairs(self.m_List) do
		-- printx(Info.Id,Info.Value)
	end
end

function clsInsertSort:GetList()
	return self.m_List
end

function clsInsertSort:OnDestroy()
	Super(clsInsertSort).OnDestroy(self)
	self.m_List = nil
	self.m_Id2Info = nil
end

--验证逻辑  可自行写一个
function AddRandomValue()
	local function sort_func( a,b )
		if a.Value > b.Value then
			return -1 --降序
		elseif a.Value == b.Value then
			return 0
		else
			return 1
		end
	end

	--下面的东西跑个1000遍
    for m = 1,1000 do
        local InsertSortObj = clsInsertSort:New()
        InsertSortObj:OnCreate(100,sort_func)	
        local IdList = {}
        local IdArray = {}
        
        for i = 1,10 do
            local random = math.random(1,1000)

            -- print("随机种子为:",random)
            InsertSortObj:InsertValue(random,{Value = random})
            -- printx("插入:",random)
            if not IdList[random] then
                IdList[random] = true
                table.insert(IdArray,random)
            end

            if random % 2 == 0 then
                for k = 1,2 do --插入相同值
                    local j = math.random(1,1000)
                    -- printx("插入:",random+j)
                    InsertSortObj:InsertValue(random+j,{Value = random})
                    if not IdList[random+j] then
                        IdList[random+j] = true
                        table.insert(IdArray,random+j)
                    end
                end
            else
                --移除值
                local r = random % #IdArray + 1
                -- printx("remove:",r,IdArray[r])
                InsertSortObj:RemoveValueById(IdArray[r])
                -- table.remove(IdArray,r)
            end

            --验证有序
            local List = InsertSortObj:GetList()
            if #List > 1 then 
                local Info = List[1]

                for i = 2,#List do    
                    assert(Info.Value >= List[i].Value)
                    Info = List[i]
                end
            end
        end
        

        InsertSortObj:Traverse()
        InsertSortObj:OnDestroy()
    end
	printx("验证成功")
end




--调表实现
local MAXLEVEL = 32    --最大32层
local P = 0.25         --起始均衡

local function SORTSET_SORT_FUNC( a,b )
    if a > b then 
        return 1
    elseif a == b then
        return 0
    else
        return -1
    end
end

local function randomLevel()
    local level = 1
    while(math.random(1, 0xffff) < P * 0xffff) do
        level = level + 1
    end
    return level < MAXLEVEL and level or MAXLEVEL
end

--level 层数
-- key 唯一键
-- value 值
local function createNode(Level, Key, Value)
    local Node = {key = Key, value = Value, level = {}, backward = nil}
    for lv = 1, Level do
        table.insert(Node.level, {forward = nil, span = 0})
    end
    return Node
end

clsSortSet = clsObject:Inherit("clsSortSet")
function clsSortSet:OnCreate(MaxSize,Func)
	Super(clsSortSet).OnCreate(self)
    self.m_SortFunc = Func or SORTSET_SORT_FUNC
	assert(type(self.m_SortFunc) == "function")
    self.m_Header = createNode(MAXLEVEL) --头节点
    self.m_Tail = nil;   --尾结点
    self.m_MaxSize = MaxSize
    self.m_Length = 0; --当前长度
    self.m_Level = 1; --当前最大层数
	self.m_AllObjs = {} --所有的节点 键值对形式
end

function clsSortSet:OnDestroy()
	Super(clsSortSet).OnDestroy(self)
	self.m_SortFunc = nil
	self.m_Header = nil
    self.m_Tail = nil;   --尾结点
	self.m_AllObjs = nil --所有的节点 键值对形式
end

--插入节点 内部接口
function clsSortSet:InsertNode(Key,Value)
    -- printx(Key,Value)
	local update = {}
    local rank   = {}

    local x = self.m_Header
    for i = self.m_Level, 1, -1 do
        --找到所有level中的节点位置
        rank[i] = i == self.m_Level and 0 or rank[i+1]  --{[32] = 0,[31] = 0,...[32] = 0}
        while x.level[i].forward and self.m_SortFunc(x.level[i].forward.value, Value) >= 0 do
            rank[i] = rank[i] + x.level[i].span
            x = x.level[i].forward
        end
        update[i] = x
    end

    --有时间完善插入是否存在对应key
    local level = randomLevel()
    -- local level = 1
    if level > self.m_Level then
        for i = self.m_Level + 1, level do
            rank[i] = 0
            update[i] = self.m_Header
            update[i].level[i].span = self.m_Length
        end
        self.m_Level = level
    end
    x = createNode(level, Key, Value)
    for i = 1, level do
        x.level[i].forward = update[i].level[i].forward
        update[i].level[i].forward = x

        x.level[i].span = update[i].level[i].span - (rank[1] - rank[i])
        update[i].level[i].span = (rank[1] - rank[i]) + 1
    end

    for i = level + 1, self.m_Level do
        update[i].level[i].span = update[i].level[i].span + 1
    end

    x.backward = update[1] ~= self.m_Header and update[1]
    if x.level[1].forward then
        x.level[1].forward.backward = x
    else
        self.m_Tail = x
    end
    -- table.print(self.m_Header)
    self.m_Length = self.m_Length + 1
    return x
end


--获取对应排名
function clsSortSet:GetRank(Key, Value)
    local rank = 0
    local x
    x = self.m_Header
    for i = self.m_Level, 1, -1 do
        -- while x.level[i].forward and (self.m_SortFunc(x.level[i].forward.value, Value) > 0 or (self.m_SortFunc(x.level[i].forward.value, Value) == 0 and x.level[i].forward.key ~= Key)) do
		while x.level[i].forward and self.m_SortFunc(x.level[i].forward.value, Value) > 0 do
            rank = rank + x.level[i].span
            x = x.level[i].forward
        end
        if x.level[i].forward and x.level[i].forward.value and x.level[i].forward.key == Key and x.level[i].forward.value == Value then
            rank = rank + x.level[i].span
            return rank
        end
    end
    return 0
end

--获取对应排名的元素
function clsSortSet:GetNodeByRank(Rank)
    if Rank <= 0 or Rank > self.m_Length then
        return
    end
    local traversed = 0
    local x = self.m_Header
    for i = self.m_Level, 1, -1 do
        while x.level[i].forward and traversed + x.level[i].span <= Rank do
            traversed = traversed + x.level[i].span
            x = x.level[i].forward
        end
        if traversed == Rank then
            return x
        end
    end
end

--获取对应排名元素的value
function clsSortSet:GetNodeValueByRank(Rank)
	local Node = self:GetNodeByRank(Rank)
	return Node and Node.value
end

--delete的内部函数
function clsSortSet:DeleteNode(Node, Update)
    for i = 1, self.m_Level do
        if Update[i].level[i].forward == Node then
            Update[i].level[i].span = Update[i].level[i].span + Node.level[i].span - 1
            Update[i].level[i].forward = Node.level[i].forward
        else
            Update[i].level[i].span = Update[i].level[i].span - 1
        end
    end
    -- table.print(Update)
    if Node.level[1].forward then
        Node.level[1].forward.backward = Node.backward
    else
        self.m_Tail = Node.backward
        -- printx("new Tail:",self.m_Tail)
    end
    while self.m_Level > 2 and not self.m_Header.level[self.m_Level -1].forward do
        self.m_Level = self.m_Level - 1
    end
    self.m_Length = self.m_Length - 1
end

--内部接口
function clsSortSet:Delete(Key, Value,IsAdd)
    local update = {}
    local x = self.m_Header
    for i = self.m_Level, 1, -1 do
        -- while x.level[i].forward and (self.m_SortFunc(x.level[i].forward.value, Value) > 0 or (self.m_SortFunc(x.level[i].forward.value, Value) == 0 and x.level[i].forward.key ~= Key)) do
		while x.level[i].forward and self.m_SortFunc(x.level[i].forward.value, Value) > 0 do
            x = x.level[i].forward
        end
        update[i] = x
    end

    --确保对象的正确
    x = x.level[1].forward
    -- table.print(x)
    if x and x.key == Key and x.value == Value then
		local OldRank = self:Rank(Key)
        self:DeleteNode(x, update)
		self:DeleteSuccess(Key, IsAdd, OldRank, Value)
        return true
    end
    return false
end

--获取范围内的key
function clsSortSet:Range(Start, Stop)
    local node = self:GetNodeByRank(Start)
    local result = {}
    local len = Stop - Start + 1
    local n = 0
    while node and n < len do
        n = n + 1
        result[#result+1] = node.key
        node = node.level[1].forward
    end
    return result
end

function clsSortSet:GetRangeData(Start, Stop)
	local node = self:GetNodeByRank(Start)
    local result = {}
    local len = Stop - Start + 1
    local n = 0
    while node and n < len do
        n = n + 1
		table.insert(result,node.value)
        node = node.level[1].forward
	end
	return result
end

function clsSortSet:GetAllRangeData()
	local Start = 1
	local Stop = self:Count()
	return self:GetRangeData(Start, Stop)
end

--value可以是自定义结构, 但自己要定义好比较结构
--外部接口
function clsSortSet:Add(Key, Value)
    if not Key or not Value then
        return
    end
    local oldValue = self.m_AllObjs[Key]
    if oldValue then
        local IsSucc = self:Delete(Key, oldValue, true)
		if not IsSucc then
			_RUNTIME_ERROR("[clsSortSet:Add] delet failed!!! Key=%s,Value=%s", tostring(Key), tostring(Value))
		end
	end
    self:InsertNode(Key, Value)
    self.m_AllObjs[Key] = Value
	self:AddSuccess(Value)

    if self.m_Length > self.m_MaxSize then
        self:DeleteTail()
    end
end

--通过key值获取对应value
--外部接口
function clsSortSet:GetByKey(Key)
    return self.m_AllObjs[Key]
end

--通过key获取对应排名
--外部接口
function clsSortSet:Rank(Key)
    local value = self.m_AllObjs[Key]
    if not value then
        return 0
    end
    local rank = self:GetRank(Key, value)
    return  rank > 0 and rank or 0
end

--获取排行榜数量
function clsSortSet:Count()
    return self.m_Length
end

--根据key删除元素
function clsSortSet:Remove(Key)
    local oldValue = self.m_AllObjs[Key]
    -- printx(Key,oldValue)
    if oldValue then
        self:Delete(Key, oldValue)
        self.m_AllObjs[Key] = nil
    end
end

function clsSortSet:DeleteTail()
    -- printx("DeleteTail:",self.m_Tail.key)
	if self.m_Tail then
		self:Remove(self.m_Tail.key)
	end
end

--从头开始打印所有数据
function clsSortSet:Print()
    -- printx("print start")
    local x = self.m_Header
    local i = 0
    while x.level[1].forward do
        x = x.level[1].forward
        i = i + 1
		local value = x.value
        printx("排名:".. i .."  Id: ".. value.Id  .. "  Value: " .. value.Value)
    end
    -- printx("print end")
end

function clsSortSet:AddSuccess(Node)
	
end

function clsSortSet:DeleteSuccess(Key, IsAdd, OldRank, RankInfo)

end


-----------------------------------------------------------------
-- 双向循环队列
-----------------------------------------------------------------
--[[
	· table实现的双向循环队列（顺序存储结构）
	· 适用于（1. 最大长度固定 2. 从队列一端插入，另一端删除）的需求
	· 避免了在数组头部删除/插入时的元素迁移操作。
	· 虽然直接用链表也可以，但是直接用数组实现可以减少每个节点的内存消耗。
	· 因为没有了元素迁移的操作，也就可以兼容单个元素的碎片存盘了（如果是单纯的数组，从头部删除一个元素后，所有元素的下标都会变化，就无法单个元素碎片存盘）

	注意：
	1. _MaxSize会比队列长度大1，用于区分队列满的情况，实际可存储的元素上限=_MaxSize-1
	2. 插入/删除会返回SubPaths数据，用于碎片存盘（遍历SubPaths，往table头部插入父节点路径即可，具体可参考act_secret.lua） 。

	问题：
	1. 循环队列的数组下标是从0开始的，和lua的从1开始不一致，暂时不清楚这样是否会引入其他问题。
	2. ipairs 遍历：k 是front->rear，是否应该把k转成 从1->maxsize ？
]]
clsCircularQueue = clsObject:Inherit("clsCircularQueue")
function clsCircularQueue:OnCreate(MaxSize)
	Super(clsCircularQueue).OnCreate(self)
	self._Oci = {
		_MaxSize = MaxSize + 1,
		_Data    = {},
		_Front   = 0,
		_Rear    = 0,
	}
end

function clsCircularQueue:SetOci(Oci)
	self._Oci = Oci
end

function clsCircularQueue:GetOci()
	return self._Oci
end

-- 尾部插入
function clsCircularQueue:InsertLast(Value, IsNeedUpdate)
	if not Value then return false end
	if self:IsFull() then return false end
	
	local Oci = self._Oci
	local Key = Oci._Rear
	Oci._Data[Oci._Rear] = Value
	Oci._Rear = (Oci._Rear + 1) % Oci._MaxSize

	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Rear", _V=Oci._Rear},
			{"_Data", Key, _V=Value},
		}
	end
	return true, SubPaths
end

-- 头部插入
function clsCircularQueue:InsertFront(Value, IsNeedUpdate)
	if not Value then return false end
	if self:IsFull() then return false end

	local Oci = self._Oci
	Oci._Front = (Oci._Front + Oci._MaxSize - 1) % Oci._MaxSize
	Oci._Data[Oci._Front] = Value

	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Front", _V=Oci._Front},
			{"_Data", Oci._Front, _V=Value},
		}
	end
	return true, SubPaths
end

-- 尾部删除
function clsCircularQueue:DelLast(IsNeedUpdate)
	if self:IsEmpty() then return false end

	local Oci = self._Oci
	Oci._Rear = (Oci._Rear + Oci._MaxSize - 1) % Oci._MaxSize
	Oci._Data[Oci._Rear] = nil

	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Rear", _V=Oci._Rear},
			{"_Data", Oci._Rear, _V=nil},
		}
	end
	return true, SubPaths
end

-- 头部删除
function clsCircularQueue:DelFront(IsNeedUpdate)
	if self:IsEmpty() then return false end

	local Oci = self._Oci
	local Key = Oci._Front
	Oci._Data[Oci._Front] = nil
	Oci._Front = (Oci._Front + 1) % Oci._MaxSize

	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Front", _V=Oci._Front},
			{"_Data", Key, _V=nil},
		}
	end
	return true, SubPaths
end

function clsCircularQueue:GetFront()
	if self:IsEmpty() then return false end

	local Oci = self._Oci
	return Oci._Data[Oci._Front]
end

function clsCircularQueue:GetLast()
	if self:IsEmpty() then return false end

	local Oci = self._Oci
	return Oci._Data[(Oci._Rear + Oci._MaxSize - 1) % Oci._MaxSize]
end

function clsCircularQueue:IsEmpty()
	local Oci = self._Oci
	return Oci._Front == Oci._Rear
end

function clsCircularQueue:IsFull()
	local Oci = self._Oci
	return (Oci._Rear+1)%Oci._MaxSize == Oci._Front
end

function clsCircularQueue:Len()
	local Oci = self._Oci
	return (Oci._Rear-Oci._Front+Oci._MaxSize)%Oci._MaxSize
end

function clsCircularQueue:Clear()
	local Oci = self._Oci
	Oci._Data    = {}
	Oci._Front   = 0
	Oci._Rear    = 0
end

function clsCircularQueue:ipairs()
	local function next(QueueObj, k)
		local Oci = QueueObj._Oci
		if not k then
			k = Oci._Front
			local v = Oci._Data[k]
			if v then return k, v end
		else
			k = (k+1)%Oci._MaxSize
			local v= Oci._Data[k]
			if v then return k, v end
		end
	end
	return next, self
end

function clsCircularQueue:ToString()
	local Oci = self._Oci
	local MaxSize = Oci._MaxSize - 1
	MaxSize = MaxSize < 0 and 0 or MaxSize
	return string.format("MaxSize=%s, Len=%d, Front=%s, Rear=%s", tostring(MaxSize), self:Len(), tostring(Oci._Front), tostring(Oci._Rear))
end

function clsCircularQueue:Dump()
	_RUNTIME_INFO("[clsCircularQueue:Dump]Obj=%s, start-----------------", ToString(self))
	for k, v in self:ipairs() do
		_RUNTIME_INFO("[clsCircularQueue:Dump] k=%d, v=%s",k, Serialize(v))
	end
	_RUNTIME_INFO("[clsCircularQueue:Dump] end------------------------------------------")
end

function clsCircularQueue:OnDestroy()
	Super(clsCircularQueue).OnDestroy(self)
	self._Oci = nil
end

-------------------------------------------------------------------------------------------------
-- 双向循环队列非obj的封装版本
-------------------------------------------------------------------------------------------------
function CirQueue_Create(MaxSize)
	return {
		_MaxSize = MaxSize + 1,
		_Data    = {},
		_Front   = 0,
		_Rear    = 0,
	}
end

-- 尾部插入
function CirQueue_InsertLast(Value, Oci, IsNeedUpdate)
	if not Value then return false end
	if CirQueue_IsFull(Oci) then return false end
	
	local Key = Oci._Rear
	Oci._Data[Oci._Rear] = Value
	Oci._Rear = (Oci._Rear + 1) % Oci._MaxSize
	
	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Rear", _V=Oci._Rear},
			{"_Data", Key, _V=Value},
		}
	end
	return true, SubPaths
end

-- 头部插入
function CirQueue_InsertFront(Value, Oci, IsNeedUpdate)
	if not Value then return false end
	if CirQueue_IsFull(Oci) then return false end
	
	Oci._Front = (Oci._Front + Oci._MaxSize - 1) % Oci._MaxSize
	Oci._Data[Oci._Front] = Value
	
	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Front", _V=Oci._Front},
			{"_Data", Oci._Front, _V=Value},
		}
	end
	return true, SubPaths
end

-- 尾部删除
function CirQueue_DelLast(Oci, IsNeedUpdate)
	if CirQueue_IsEmpty(Oci) then return false end
	
	Oci._Rear = (Oci._Rear + Oci._MaxSize - 1) % Oci._MaxSize
	Oci._Data[Oci._Rear] = nil
	
	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Rear", _V=Oci._Rear},
			{"_Data", Oci._Rear, _V=nil},
		}
	end
	return true, SubPaths
end

-- 头部删除
function CirQueue_DelFront(Oci, IsNeedUpdate)
	if CirQueue_IsEmpty(Oci) then return false end
	
	local Key = Oci._Front
	Oci._Data[Oci._Front] = nil
	Oci._Front = (Oci._Front + 1) % Oci._MaxSize
	
	local SubPaths
	if IsNeedUpdate then
		SubPaths = {
			{"_Front", _V=Oci._Front},
			{"_Data", Key, _V=nil},
		}
	end
	return true, SubPaths
end

function CirQueue_GetFront(Oci)
	if CirQueue_IsEmpty(Oci) then return false end
	
	return Oci._Data[Oci._Front]
end

function CirQueue_GetLast(Oci)
	if CirQueue_IsEmpty(Oci) then return false end
	
	return Oci._Data[(Oci._Rear + Oci._MaxSize - 1) % Oci._MaxSize]
end

function CirQueue_IsEmpty(Oci)
	return Oci._Front == Oci._Rear
end

function CirQueue_IsFull(Oci)
	return (Oci._Rear+1)%Oci._MaxSize == Oci._Front
end

function CirQueue_Len(Oci)
	return (Oci._Rear-Oci._Front+Oci._MaxSize)%Oci._MaxSize
end

function CirQueue_Clear(Oci)
	Oci._Data    = {}
	Oci._Front   = 0
	Oci._Rear    = 0
end

function CirQueue_ipairs(Oci)
	local function next(QueueData, k)
		if not k then
			k = QueueData._Front
			local v = QueueData._Data[k]
			if v then return k, v end
		else
			k = (k+1)%QueueData._MaxSize
			local v= QueueData._Data[k]
			if v then return k, v end
		end
	end
	return next, Oci
end

function CirQueue_tostring(Oci)
	local MaxSize = Oci._MaxSize - 1
	MaxSize = MaxSize < 0 and 0 or MaxSize
	local QueueStr = string.format("MaxSize=%s, Len=%d, Front=%s, Rear=%s", tostring(MaxSize), CirQueue_Len(Oci), tostring(Oci._Front), tostring(Oci._Rear))
	return QueueStr
end

function CirQueue_Dump(Oci)
	local Queue = CirQueue_tostring(Oci)
	_RUNTIME_INFO("[CirQueue_Dump]Queue=%s, start-----------------", Queue)
	for k, v in CirQueue_ipairs(Oci) do
		_RUNTIME_INFO("[CirQueue_Dump] k=%d, v=%s",k, Serialize(v))
	end
	_RUNTIME_INFO("[CirQueue_Dump] end------------------------------------------")
end

_G.CirQueue_Create      = CirQueue_Create
_G.CirQueue_InsertLast  = CirQueue_InsertLast
_G.CirQueue_InsertFront = CirQueue_InsertFront
_G.CirQueue_DelLast     = CirQueue_DelLast
_G.CirQueue_DelFront    = CirQueue_DelFront
_G.CirQueue_GetFront    = CirQueue_GetFront
_G.CirQueue_GetLast     = CirQueue_GetLast
_G.CirQueue_IsEmpty     = CirQueue_IsEmpty
_G.CirQueue_IsFull      = CirQueue_IsFull
_G.CirQueue_Len         = CirQueue_Len
_G.CirQueue_Clear       = CirQueue_Clear
_G.CirQueue_ipairs      = CirQueue_ipairs
_G.CirQueue_tostring    = CirQueue_tostring
_G.CirQueue_Dump        = CirQueue_Dump